#include "stack_bintree.h"
#include "BinTree_int.h"

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

static const int MaxSize = 1000;

BinTree bintree_create(int data) {
	BinTree bt = (BinTree)malloc(sizeof(_BNode));
	assert(bt);

	bt->data = data;
	bt->left = bt->right = NULL;
	return bt;
}

BinTree bintree_free(BinTree bt) {
	if (bt)
		free(bt);
	return NULL;
}

BinTree bintree_insert(BinTree bt, int value) {
	if (bt == NULL) {
		return bintree_create(value);
	}
	else{
		if (value < bt->data)
			bt->left = bintree_insert(bt->left, value);
		else if (value > bt->data)
			bt->right = bintree_insert(bt->right, value);
	}
	return bt;
}
BinTree bintree_min(BinTree bt) {
	if (!bt)
		return bt;
	while (bt->left)
		bt = bt->left;
	return bt;
}
BinTree bintree_max(BinTree bt) {
	if (!bt)
		return bt;
	while (bt->right)
		bt = bt->right;
	return bt;
}

void bintree_preorder_traversal(BinTree bt) {
	BinTree t = bt;
	StackBT s = stackbt_create(MaxSize);
	while (t || !stackbt_is_empty(s)) {
		while (t)
		{
			printf("%5d", t->data);
			stackbt_push(s, t);
			t = t->left;
		}
		if (!stackbt_is_empty(s)) {
			t = stackbt_pop(s);
			t = t->right;
		}
	}
	printf("\n");
}

void bintree_inorder_traversal(BinTree bt) {
	BinTree t = bt;
	StackBT s = stackbt_create(MaxSize);
	while (t || !stackbt_is_empty(s)) {
		while (t)
		{
			stackbt_push(s, t);
			t = t->left;
		}
		if (!stackbt_is_empty(s)) {
			t = stackbt_pop(s);
			printf("%5d", t->data);
			t = t->right;
		}
	}
	printf("\n");
}

void bintree_postorder_traversal(BinTree bt) {
	BinTree t = bt;
	StackBT s1 = stackbt_create(MaxSize);
	StackBT s2 = stackbt_create(MaxSize);
	stackbt_push(s1, t);
	while (!stackbt_is_empty(s1)) {
		t = stackbt_pop(s1);
		stackbt_push(s2, t);
		if (t->left)
			stackbt_push(s1, t->left);
		if (t->right)
			stackbt_push(s1, t->right);
	}
	while (!stackbt_is_empty(s2)) {
		t = stackbt_pop(s2);
		printf("%5d", t->data);
	}
	printf("\n");
}

void bintree_postorder_traversal2(BinTree bt) {
	BinTree t = bt;
	StackBT s1 = stackbt_create(MaxSize);
	StackBT s2 = stackbt_create(MaxSize);
	while (t || !stackbt_is_empty(s1)) {
		while (t)
		{
			stackbt_push(s1, t);
			stackbt_push(s2, t);
			t = t->right;
		}
		if (!stackbt_is_empty(s1)) {
			t = stackbt_pop(s1);
			t = t->left;
		}
	}
	while (!stackbt_is_empty(s2)) {
		t = stackbt_pop(s2);
		printf("%5d", t->data);
	}
	printf("\n");
}

void bintree_postorder_traversal0(BinTree bt) {
	if (bt) {
		bintree_postorder_traversal0(bt->left);
		bintree_postorder_traversal0(bt->right);
		printf("%5d", bt->data);
	}
}